package main

func main() {

	//root = [4,2,9,3,5,null,7]  深度3
	node3 := TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node5 := TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node1 := TreeNode{
		Val:   2,
		Left:  &node3,
		Right: &node4,
	}
	node2 := TreeNode{
		Val:   9,
		Left:  nil,
		Right: &node5,
	}
	root := TreeNode{
		Val:   4,
		Left:  &node1,
		Right: &node2,
	}

	//打印测试用例返回结果
	resp := maxDepth(&root)
	println(resp)

}

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/* 给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。 */

func maxDepth(root *TreeNode) int {
	if root == nil { //边界检查
		return 0
	}
	max, count := 0, 0
	max = dfs(root, max, count)
	return max

}

//前序遍历
func dfs(root *TreeNode, max, count int) int {

	if root == nil {
		return max
	}
	count++
	if max < count {
		max = count
	}
	max = dfs(root.Left, max, count)
	max = dfs(root.Right, max, count)
	count--
	return max
}

func maxDepth(root *TreeNode) int {
	if root == nil { //边界检查
		return 0
	}
	//叶结点
	if root.Left == nil && root.Right == nil {
		return 1
	}
	maxD := -1
	if root.Left != nil {
		maxD = maxDepth(root.Left)
	}
	if root.Right != nil {
		maxD = max(maxDepth(root.Right), maxD)
	}
	return maxD + 1

}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

/*
	边界条件：如果root是空，返回0， 如果root是叶结点，返回1
	除此之外的任意结点均满足：子树最大深度 即Max(左儿子右儿子)+1
*/
